package leetcode.primary;

import utils.tree.BinaryTree;
import utils.tree.Tree;
import utils.tree.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class T236 {
    Map<TreeNode,StringBuilder> map = new HashMap<>();
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root==p || root==q){
            return root;
        }
        DFS(root,new StringBuilder(""),p,q);
        String prefix = SamePrefix(map.get(p), map.get(q));
        System.out.println(prefix);
        TreeNode node = root;
        int index = 0;
        while (index<prefix.length()){
            if (prefix.charAt(index)=='0'){
                node = node.left;
            }else {
                node = node.right;
            }
            index++;
        }
        return node;
    }

    public void DFS(TreeNode node,StringBuilder str,TreeNode p,TreeNode q){

        if (node==p){
            map.put(p,new StringBuilder(str));
            System.out.println("p.prefix="+str);
        }
        if (node==q){
            map.put(q,new StringBuilder(str));
            System.out.println("q.prefix="+str);
        }

        if (map.size()==2){
            return;
        }

        if (node.left!=null){
            DFS(node.left,str.append('0'),p,q);
            str.deleteCharAt(str.length()-1);
        }
        if (node.right!=null){
            DFS(node.right,str.append('1'),p,q);
            str.deleteCharAt(str.length()-1);
        }
    }

    public String SamePrefix(StringBuilder str1,StringBuilder str2){
        System.out.println("str1="+str1+",str2="+str2);
        int index = 0;
        while (index<str1.length() && index<str2.length() &&str1.charAt(index)==str2.charAt(index)){
            index++;
        }

        return str1.substring(0,index);
    }

    public static void main(String[] args) {
        T236 t236 = new T236();
        Tree tree = new BinaryTree(new int[]{3,5,6,0,0,2,7,0,0,4,0,0,1,9,0,0,8,0,0});
        TreeNode root = tree.InitTree();
        TreeNode p = root.left;
        TreeNode q = p.right.right;
        tree.InorderTravel(root);
        TreeNode node = t236.lowestCommonAncestor(root, p, q);
        System.out.println(node.val);
    }
}

